home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_13_03 / grant / pop.cpp < prev    next >
C/C++ Source or Header  |  1994-12-22  |  3KB  |  122 lines
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <float.h>
  4. #include <assert.h>
  5. #include <string.h>
  6.  
  7. #include "pop.h"
  8. #include "random.h"
  9.  
  10. // Constructor. It creates a population of chromosomes
  11. // where the probability that each bit is true
  12. // increases with each creation, then it creates a
  13. // compliment of each of the created chromosomes.
  14.  
  15. CGAPopulation::CGAPopulation(
  16.    unsigned int Size,
  17.    unsigned int Length,
  18.    float MaxMutationRate)
  19. {
  20.    assert(Size && Length);
  21.    m_MaxSize         = Size;
  22.    m_CurrentSize     = 0;
  23.    m_Generation      = 0;
  24.    m_MaxMutationRate = MaxMutationRate;
  25.    m_Data            = new CGAChromosome*[m_MaxSize];
  26.    CGAChromosome::InitializeChromosomeClass(Length);
  27.  
  28.    for (unsigned int idx = 1; idx <= m_MaxSize / 2;
  29.         idx++) {
  30.       CGAChromosome* Temp =
  31.          new CGAChromosome(idx / (float)m_MaxSize);
  32.       CGAChromosome* CompTemp = Temp->Compliment();
  33.       Merge(Temp);
  34.       Merge(CompTemp);
  35.    }
  36. }
  37.  
  38. // Default destructor
  39.  
  40. CGAPopulation::~CGAPopulation()
  41. {
  42.    for (unsigned int idx = 0; idx < m_MaxSize; idx++) {
  43.       delete m_Data[idx];
  44.    }
  45.    delete m_Data;
  46. }
  47.  
  48. // Merge sort the new chromosome, assume that there no
  49. // holes in the array.
  50.  
  51. void CGAPopulation::Merge(
  52.    CGAChromosome* NewChromosome)
  53. {
  54.    assert(m_CurrentSize < m_MaxSize);
  55.    for (unsigned int idx = 0; idx < m_CurrentSize;
  56.         idx++) {
  57.       if (NewChromosome->GetFitness() >
  58.           m_Data[idx]->GetFitness()) {
  59.          break;
  60.       }
  61.    }
  62.    memmove(&m_Data[idx + 1], &m_Data[idx],
  63.            sizeof(m_Data) * (m_CurrentSize - idx));
  64.    m_Data[idx] = NewChromosome;
  65.    m_CurrentSize++;
  66. }
  67.  
  68. // These functions randomly select a chromosome from
  69. // the ranked array, where the probability of selection
  70. // is related to the individual's position in the
  71. // array. ReplaceChromosome calculates an individual's
  72. // probability for replacement by Rank(X) / Total.
  73. // GetParent calculates an individual's probability for
  74. // parenthood by (Total - Rank(X)) / Total).
  75.  
  76. CGAChromosome* CGAPopulation::GetParent()
  77. {
  78.    float   Selection;
  79.  
  80.    do {
  81.       Selection = Rand0UpTo1();
  82.    } while (Flip(Selection));
  83.    return m_Data[(int)(Selection * m_MaxSize)];
  84. }
  85.  
  86. //  Replace a poor chromosome with the new one.
  87.  
  88. void CGAPopulation::ReplaceChromosome(
  89.    CGAChromosome* NewChromosome)
  90. {
  91.    float   Selection;
  92.  
  93.    do {
  94.       Selection = Rand0UpTo1();
  95.    } while (Flip(Selection));
  96.  
  97.    unsigned int idx = m_MaxSize - 
  98.       (int)(Selection * m_MaxSize) - 1;
  99.    delete m_Data[idx];
  100.    memmove(&m_Data[idx], &m_Data[idx + 1],
  101.            sizeof(m_Data) * (m_CurrentSize - idx - 1));
  102.    m_CurrentSize--;
  103.    Merge(NewChromosome);
  104. }
  105.  
  106. // Create two offspring and replace two members of the
  107. // chromosome array.
  108.  
  109. void CGAPopulation::CreateNextGeneration(void)
  110. {
  111.    CGAChromosome *Parent1, *Parent2, *Child1, *Child2;
  112.  
  113.    Parent1 = GetParent();
  114.    Parent2 = GetParent();
  115.    Crossover(Parent1, Parent2, Child1, Child2,
  116.              CalcSimilarityRatio(Parent1, Parent2) *
  117.              m_MaxMutationRate);
  118.    ReplaceChromosome(Child1);
  119.    ReplaceChromosome(Child2);
  120.    m_Generation++;
  121. }
  122.